\section{数论函数及其值}


\begin{frame}{数论函数及其值}
第三章 §3.6 和本章已讨论了数论(算术)函数。 我们进一步讨论， 要用到定积分的定义。 定积分的几何意义是函数曲线下的面积，是梯形条面积之和，故与和式相差不大。

我们知道， 数论 (算术) 函数 $f, g$ 之间有两种乘积： (1) 诸点（普通）乘积 $f g$, 也记为 $f \cdot g$, 即 $(f g)(n)=(f \cdot g)(n)=f(n) g(n)$ (对任意整数 $n$). Dirichlet 卷积 $f * g$, 即
\[
  \left(f {*} g\right)(n)=\sum_{d \mid n} f(d) g(n / d)=\sum_{d_{1} d_{2}=n} f\left(d_{1}\right) g\left(d_{2}\right).
\]
Dirichlet 卷积在初等数论中频繁出现。 我们在 § 3.6 也看到：

算术函数集 $\mathscr{F}$ 对 Dirichlet 卷积（和普通诸点加法）是含么交换环 $(\mathscr{F},+, *)$,称为 \emph{Dirichlet (卷积) 函数环}。 其卷积单位元为 $\varepsilon$, 加法单位元为 $0$ (即取值恒为 $0$ 的函数), 而函数 $\mu$ 与 $1$ 互为逆。
\end{frame}

\begin{frame}
  \begin{theorem}%定理1
  记 $L(n)=\log n$ (即将对数函数作为算数函数 $L$ ，取值于自然数). 则
\[
  L \cdot(f * g)=(L \cdot f) * g+f *(L \cdot g).
\]
此性质被称为：“用对数函数诸点乘”是 Dirichlet (卷积)函数环的微分(求导函数).
\end{theorem}

\begin{proof}
 对任意正整数 $d \mid n$ ，有
 \[
   L(n)=L(d \cdot n / d)=L(d)+L(n / d).
 \]
 故
 \[
   \begin{aligned}
   (L \cdot(f * g))(n) & =L(n) \sum_{d \| n} f(d) g(n / d)=\sum_{d \mid n} L(n) f(d) g(n / d) \\
 & =\sum_{d \mid n}(L(d)+L(n / d)) f(d) g(n / d) \\
 & =\sum_{d \| n} L(d) f(d) g(n / d)+\sum_{d \mid n} L(n / d) f(d) g(n / d) \\
 & =(L \cdot f) * g+f *(L \cdot g) .
 \end{aligned}
 \]
 \end{proof}
 \end{frame}

 \begin{frame}
   \begin{theorem}%定理2
   (1) 设整数 $a<b, f(x)$ 单调， 则
 \[
   \min (f(a), f(b)) \leqslant \sum_{n=a}^{b} f(n)-\int_{a}^{b} f(t) \mathrm{d} t \leqslant \max (f(a), f(b)).
 \]

  (2) 设实数 $c<\lfloor d\rfloor$ (整数部分), $f(x)$ 单调且非负， 则
\[
  \left|\sum_{c<n \leqslant d} f(n)-\int_{c}^{d} f(t) \mathrm{d} t\right| \leqslant \max (f(c), f(d)).
\]

(3) 设 $f(x)$ 分段单调且非负， 则
\[
F(x)=\sum_{n=1}^{x} f(n)=\int_{1}^{x} f(t) \mathrm{d} t+O(1)
\]
（其中 $O(g(x))$ 表示一个函数， 使 $O(g(x)) / g(x)$ 有界 $(x \rightarrow \infty$ 时)).
\end{theorem}

 \end{frame}

 \begin{frame}

\begin{proof}
 (1) 若 $f(x)$ 单调上升， 则
 \[
   f(n) \leqslant \int_{n}^{n+1} f(t) \mathrm{d} t \leqslant f(n+1), \quad f(a) \leqslant \sum_{n=a}^{b} f(n)-\int_{a}^{b} f(t) \mathrm{d} t \leqslant f(b).
 \]
 同理讨论 $f(x)$ 递降情形。

 (2) 记 $a=\lfloor c\rfloor+1, b=\lfloor d\rfloor$, 则 $c<a \leqslant b \leqslant d$. 若 $f(x)$ 单调上升， 则
 \[
   \begin{aligned}
     \sum_{c<n \leqslant d} f(n)&= \sum_{a \leqslant n \leqslant b} f(n) \leqslant \int_{a}^{b} f(t) \mathrm{d} t+f(b) \int_{c}^{d} f(t) \mathrm{d} t+f(d), \\
 \sum_{c<n \leqslant d} f(n) & \geqslant \int_{a}^{b} f(t) \mathrm{d} t+f(a) \geqslant \int_{c}^{d} f(t) \mathrm{d} t-\int_{b}^{d} f(t) \mathrm{d} t+f(a)-\int_{c}^{a} f(t) \mathrm{d} t \\
 & \geqslant \int_{c}^{d} f(t) \mathrm{d} t-f(c), \\
 & \left|\sum_{c<n \leqslant d} f(n)-\int_{c}^{d} f(t) \mathrm{d} t\right| \leqslant f(c).
 \end{aligned}
 \]
 同理讨论 $f(x)$ 递降情形。

 (3) 设 $f(x)$ 在 $[1, \infty)$ 是分段单调且非负， 则 $f(x)$ 有界， 故由 (2) 则得 (3).
 \end{proof}
 \end{frame}

 \begin{frame}
  \begin{theorem}%定理3
  $\sum_{n \leqslant x} \log n=x \log x-x+O(\log x)$.
\end{theorem}

\begin{proof}
 由定理 1, $\int_{1}^{x} \log t \mathrm{~d} t \leqslant \sum_{n \leqslant x} \log n \leqslant \int_{1}^{x} \log t \mathrm{~d} t+\log x$, 而 $\int_{1}^{x} \log t \mathrm{~d} t=x \log x-x$.
 \end{proof}

 \begin{theorem}%定理4
 $\sum_{n \leqslant x} \frac{\log ^{r} n}{n}=\frac{1}{r+1} \log ^{r+1} x+O(1)$ (这里 $r$ 为非负整数， $x \geqslant 1$).
 \end{theorem}

 \begin{proof}
  $f(t)=\log ^{t} t / t$ 在 $[1, \infty)$ 非负且分段单调， 在 $t=\mathrm{e}^{t}$ 取极大值为 $(r / e)^{r}$. 由定理 1 得
\[
\sum_{n \leqslant x} \frac{\log ^{r} n}{n}=\int_{1}^{x} \frac{\log ^{r} t}{t} \mathrm{~d} t+O(1)=\frac{1}{r+1} \log ^{r+1} x+O(1)
\]
\end{proof}
\begin{theorem}%定理5
$\sum_{n \leqslant x} \frac{\log ^{k}(x / n)}{n}=\frac{1}{k+1} \log ^{k+1} x+O\left(\log ^{k} x\right)$ （这里 $k$ 为非负整数， $x \geqslant 1$).
 \end{theorem}

\end{frame}
\begin{frame}

 \begin{proof}
  将 $\log ^{k}(x / n)=(\log x-\log n)^{k}$ 二项式展开， 再用定理 3, 得
\[
  \begin{aligned}
  \sum_{n \leqslant x} \frac{\log ^{k}(x / n)}{n} & =\sum_{n \leqslant x} \frac{(\log x-\log n)^{k}}{n}=\sum_{n \leqslant x} \frac{1}{n} \sum_{r=0}^{k} \binom{k}{r} \log ^{k-r} x(-\log n)^{r} \\
& =\sum_{r=0}^{k} \binom{k}{r} \log ^{k-r} x \sum_{n \leqslant x} \frac{1}{n} \sum_{r=0}^{k}(-\log n)^{r} \\
& =\sum_{r=0}^{k} \binom{k}{r}(-1)^{r} \log ^{k-r} x\left[\frac{1}{r+1} \log ^{r+1} x+O(1)\right] \\
& =\sum_{r=0}^{k} \binom{k}{r} \frac{(-1)^{r}}{r+1} \log ^{k+1} x+O\left(\sum_{r=0}^{k} \binom{k}{r} \log ^{k-r} x\right) \\
& =\frac{1}{k+1} \log ^{k+1} x+O\left(\log ^{k} x\right)
\end{aligned}
\]
最后一步是因为 (见本节习题 2)
\[
\sum_{r=0}^{k} \binom{k}{r} \frac{(-1)^{r}}{r+1}=\frac{1}{k+1}
\]
\end{proof}
\end{frame}

\begin{frame}
  \begin{theorem}%定理6
  设 $k$ 为正整数， 则
\[
\sum_{n_{1} \cdots n_{k} \leqslant x} \frac{1}{n_{1} \cdots n_{k}}=\frac{1}{k!} \log ^{k} x+O\left(\log ^{k-1} x\right)
\]
左边的求和符号是对满足 $n_{1} \cdots n_{k} \leqslant x$ 的所有 $k$-正整数组 $\left(n_{1}, \cdots, n_{k}\right)$ 求和。
\end{theorem}

\begin{proof}
 对 $k$ 归纳。 当 $k=1$, 在定理 4 中令 $r=0$ 则得。 设定理对 $k$ 成立。
 \[
   \begin{aligned}
   \sum_{n_{1} \cdots n_{k+1} \leqslant x} \frac{1}{n_{1} \cdots n_{k+1}} & =\sum_{n_{k+1} \leqslant x} \frac{1}{n_{k+1}} \sum_{n_{1} \cdots n_{k} \leqslant x / n_{k+1}} \frac{1}{n_{1} \cdots n_{k}} \\
 & =\sum_{n_{k+1} \leqslant x} \frac{1}{n_{k+1}}\left[\frac{1}{k!} \log ^{k} x / n_{k+1}+O\left(\log ^{k-1} x / n_{k+1}\right)\right] \\
 & =\sum_{n_{k+1} \leqslant x} \frac{1}{k!n_{k+1}}\left(\log x-\log n_{k+1}\right)^{k}+O\left(\log ^{k-1} x \sum_{n_{k+1} \leqslant x} \frac{1}{n_{k+1}}\right) \\
 & =\sum_{n_{k+1} \leqslant x} \frac{1}{k!n_{k+1}}\left(\log x-\log n_{k+1}\right)^{k}+O\left(\log ^{k} x\right) .
 \end{aligned}
 \]
 \end{proof}
 \end{frame}

 \begin{frame}
   \begin{proof}[续]
 再由二项式展开和定理 4 计算主项， 得
 \[
   \begin{aligned}
   \sum_{n \leqslant x} \frac{1}{k!n}(\log x-\log n)^{k} & =\sum_{n \leqslant x} \frac{1}{k!n} \sum_{r=0}^{k} \binom{k}{r} \log ^{k-r} x(-\log n)^{r} \\
 & =\sum_{r=0}^{k} \frac{(-1)^{r}}{k!} \binom{k}{r} \log ^{k-r} x \sum_{n \leqslant x} \frac{\log ^{\prime} n}{n} \\
 & =\sum_{r=0}^{k} \frac{(-1)^{r}}{k!} \binom{k}{r} \log ^{k-r} x\left[\frac{1}{r+1} \log ^{r+1} x+O(1)\right] \\
 & =\frac{1}{k!} \log ^{k+1} x \sum_{r=0}^{k} \binom{k}{r} \frac{(-1)^{r}}{r+1}+O\left(\log ^{k} x\right) \\
 & =\frac{1}{(k+1)!} \log ^{k+1} x+O\left(\log ^{k} x\right)
 \end{aligned}
 \]
 最后一步用到习题 2.
 \end{proof}
 \end{frame}

 \begin{frame}
   \begin{comment*}%评述
   数论伊甸园最初的人门钥匙， 本书已给出。 不需任何预备， 不要他人引荐， 开初也很易起步， 简单有趣。 顺此人门寻径， 赏花攀柳品果， 即可渐人佳境， 领略神界风光。 数论， 被誉为最纯粹的科学。 是 “数字化”始祖， “软件”之最。 数学王子 Gauss 有名言：
   \begin{quote}
    “数学是诸科学之女皇， 数论是数学之女皇。 她经常屈尊谦和地帮助天文学和所有自然科学， 但是无论在哪方面， 她都有权位居至尊。"
  \end{quote}
   (As quoted in Gauss zum Gedächtniss (1856) by Wolfgang Sartorius von Waltershausen: 
 Mathematics is the queen of sciences and number theory is the queen of mathematics. She often condescends to render service to astronomy and other natural sciences, but in all relations she is entitled to the first rank.)

 数论， 引古今天下无数英才竞折腰。 到现代， 数论相关学科也是获得 Fields 奖和许多大奖最多的学科， 尊严华贵， 高高在天。 但有志事竟成， 敲门即开门。 论数者告这 “数论女王” 之情于志士痴子曰：
 \begin{poem}
  瑶池女王绮窗开， 折桂疾子何迟来：\\
 “未须八骏寻万里，天门三扣即为开!”
 \end{poem}
 \end{comment*}
 \end{frame}

